package junior.回溯法.四阶幻方;

public class 优化_暴力回溯求解 {
    static int N = 4;  // 4阶幻方：基本形式880个，翻转旋转将会有7040（大概1500ms，即：1.5秒）
    static int[] stack = new int[100];
    static int[] visit = new int[100];  // 0:未标记，1：标记
    static int top = 0;
    static int total1 = 0; // 解的个数
    public static void main(String[] args) {
        long t1 = System.currentTimeMillis();
        fun1(0);
        long t2 = System.currentTimeMillis();
        System.out.println("求解的时间："+(t2-t1)+"  ms\t"+(t2-t1)/1000+"  s");
        System.out.println("解的个数："+total1);
    }

    /**
     * n=3个元素里面取 n=3 个，进行排列，不允许重复（带标记的去重排列）
     * @param n
     */
    public static void fun1(int n){
        if(n == N*N){
            show(stack,N);
            total1++;
            return;
        }
        for (int i = 1; i <= N*N; i++) {  // C (n,r) n个里面取r个元素，进行组合
            if(visit[i] == 1){
                continue;
            }
            // 剪枝
            if(top == 3 ){// 位置：0,1,2,3
                if(34 != stack[0]+stack[1]+stack[2]+i)
                    continue;
            }
            if(top == 6 ){// 位置：0,4,8,12
                if(34 != stack[0]+stack[4]+stack[5]+i)
                    continue;
            }
            if(top == 8 ){// 位置：3,6,9,12
                if(34 != stack[3]+stack[7]+i+stack[6])
                    continue;
            }
            if(top == 10 ){// 位置：4,5,6,7
                if(34 != stack[4]+stack[9]+stack[7]+i)
                    continue;
            }
            if(top == 12 ){// 位置：8,9,10,11,
                if(34 != stack[5]+stack[8]+stack[11]+i)
                    continue;
            }

            if(top == 13 ){// 位置：1，5,9,13
                if(34 != stack[1]+stack[9]+stack[8]+i)
                    continue;
            }
            if(top == 14 ){// 位置：2,6,10,14
                if(34 != stack[2]+stack[7]+stack[11]+i)
                    continue;
            }
            if(top == 15 ){// 位置：3,7,11,15
                if(34 != stack[3]+stack[10]+stack[12]+i)
                continue;
            }
            if(top == 15 ){// 位置：0,5,10,15
                if(34 != stack[0]+stack[9]+stack[11]+i)
                    continue;
            }
            if(top == 15 ){// 位置：12,13,14,15
                if(34 != stack[6]+stack[13]+stack[14]+i)
                    continue;
            }
            stack[top++] = i;
            visit[i] = 1;  // 已经使用
            fun1(n+1);
            visit[i] = 0;  // 未使用（初试值为0）
            top--;
        }
    }
    public static void show(int[] check,int N) { // N:阶数

        System.out.println(stack[0]+"\t"+stack[1]+"\t"+stack[2]+"\t"+stack[3]);
        System.out.println(stack[4]+"\t"+stack[9]+"\t"+stack[7]+"\t"+stack[10]);
        System.out.println(stack[5]+"\t"+stack[8]+"\t"+stack[11]+"\t"+stack[12]);
        System.out.println(stack[6]+"\t"+stack[13]+"\t"+stack[14]+"\t"+stack[15]);
        System.out.println();

    }
}
